/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 晓星航
 * Date: 2023-11-21
 * Time: 8:49
 */
public class MaxPathSumInTriangle {
    public int maxPathSum(int[][] triangle) {
        int n = triangle.length;

        // 从倒数第二行开始向上更新每个节点的最大路径和
        for (int i = n - 2; i >= 0; i--) {
            for (int j = 0; j <= i; j++) {
                triangle[i][j] += Math.max(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }

        // 最后triangle[0][0]中存储的就是顶点到底部的最大路径和
        return triangle[0][0];
    }

    public static void main(String[] args) {
        int[][] triangle = {
                {9},
                {12, 15},
                {10, 6, 8},
                {2, 18, 9, 5},
                {19, 7, 10, 4, 16}
        };

        MaxPathSumInTriangle solution = new MaxPathSumInTriangle();
        int maxSum = solution.maxPathSum(triangle);
        System.out.println("最大路径和为：" + maxSum);
    }
}
